{
 "cells": [
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "聚类算法(K-MEANS):\n",
    "+ 算法接受参数 k ；然后将事先输入的n个数据\n",
    "对象划分为 k个聚类以便使得所获得的聚类满<br>\n",
    "足：同一聚类中的对象相似度较高；而不同聚\n",
    "类中的对象相似度较小。\n",
    "+ 算法思想：以空间中k个点为中心进行聚类，对\n",
    "最靠近他们的对象归类。通过迭代的方法，逐<br>\n",
    "次更新各聚类中心的值，直至得到最好的聚类\n",
    "结果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "算法步骤：\n",
    "+ 1.先从没有标签的元素集合A中随机取k个元素，作为\n",
    "k个子集各自的重心。\n",
    "+ 2.分别计算剩下的元素到k个子集重心的距离（这里的\n",
    "距离也可以使用欧氏距离），根据距离将这些元素分\n",
    "别划归到最近的子集。\n",
    "+ 3.根据聚类结果，重新计算重心（重心的计算方法是\n",
    "计算子集中所有元素各个维度的算数平均数）。\n",
    "+ 4.将集合A中全部元素按照新的重心然后再重新聚类。\n",
    "+ 5.重复第4步，直到聚类结果不再发生变化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mini Batch K-Means算法是K-Means算法的变种，采用小批\n",
    "量的数据子集减小计算时间。<br>这里所谓的小批量是指每次训练\n",
    "算法时所随机抽取的数据子集，采用这些随机产生的子集进行\n",
    "训练算法，<br>大大减小了计算时间，结果一般只略差于标准算法。\n",
    "该算法的迭代步骤有两步\n",
    "+ 1：从数据集中随机抽取一些数据形成小批量，把他们分配给最近的质心\n",
    "+ 2：更新质心与K均值算法相比，数据的更新是在每一个小的样本集上。\n",
    "Mini Batch K-Means比K-Means有更快的 收敛速度，<br>但同时\n",
    "也降低了聚类的效果，但是在实际项目中却表现得不明显。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 载入数据\n",
    "data = np.genfromtxt(\"kmeans.txt\", delimiter=\" \")\n",
    "\n",
    "plt.scatter(data[:,0],data[:,1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 训练模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 计算距离 \n",
    "def euclDistance(vector1, vector2):  \n",
    "    return np.sqrt(sum((vector2 - vector1)**2))\n",
    "  \n",
    "# 初始化质心\n",
    "def initCentroids(data, k):  \n",
    "    numSamples, dim = data.shape\n",
    "    # k个质心，列数跟样本的列数一样\n",
    "    centroids = np.zeros((k, dim))  \n",
    "    # 随机选出k个质心\n",
    "    for i in range(k):  \n",
    "        # 随机选取一个样本的索引\n",
    "        index = int(np.random.uniform(0, numSamples))  \n",
    "        # 作为初始化的质心\n",
    "        centroids[i, :] = data[index, :]  \n",
    "    return centroids  \n",
    "  \n",
    "# 传入数据集和k的值\n",
    "def kmeans(data, k):  \n",
    "    # 计算样本个数\n",
    "    numSamples = data.shape[0]   \n",
    "    # 样本的属性，第一列保存该样本属于哪个簇，第二列保存该样本跟它所属簇的误差\n",
    "    clusterData = np.array(np.zeros((numSamples, 2)))  \n",
    "    # 决定质心是否要改变的变量\n",
    "    clusterChanged = True  \n",
    "  \n",
    "    # 初始化质心  \n",
    "    centroids = initCentroids(data, k)  \n",
    "  \n",
    "    while clusterChanged:  \n",
    "        clusterChanged = False  \n",
    "        # 循环每一个样本 \n",
    "        for i in range(numSamples):  \n",
    "            # 最小距离\n",
    "            minDist  = 100000.0  \n",
    "            # 定义样本所属的簇\n",
    "            minIndex = 0  \n",
    "            # 循环计算每一个质心与该样本的距离\n",
    "            for j in range(k):  \n",
    "                # 循环每一个质心和样本，计算距离\n",
    "                distance = euclDistance(centroids[j, :], data[i, :])  \n",
    "                # 如果计算的距离小于最小距离，则更新最小距离\n",
    "                if distance < minDist:  \n",
    "                    minDist  = distance \n",
    "                    # 更新最小距离\n",
    "                    clusterData[i, 1] = minDist\n",
    "                    # 更新样本所属的簇\n",
    "                    minIndex = j  \n",
    "              \n",
    "            # 如果样本的所属的簇发生了变化\n",
    "            if clusterData[i, 0] != minIndex:  \n",
    "                # 质心要重新计算\n",
    "                clusterChanged = True\n",
    "                # 更新样本的簇\n",
    "                clusterData[i, 0] = minIndex\n",
    "  \n",
    "        # 更新质心\n",
    "        for j in range(k):  \n",
    "            # 获取第j个簇所有的样本所在的索引\n",
    "            cluster_index = np.nonzero(clusterData[:, 0] == j)\n",
    "            # 第j个簇所有的样本点\n",
    "            pointsInCluster = data[cluster_index]  \n",
    "            # 计算质心\n",
    "            centroids[j, :] = np.mean(pointsInCluster, axis = 0) \n",
    "#         showCluster(data, k, centroids, clusterData)\n",
    " \n",
    "    return centroids, clusterData  \n",
    "  \n",
    "# 显示结果 \n",
    "def showCluster(data, k, centroids, clusterData):  \n",
    "    numSamples, dim = data.shape  \n",
    "    if dim != 2:  \n",
    "        print(\"dimension of your data is not 2!\")  \n",
    "        return 1  \n",
    "  \n",
    "    # 用不同颜色形状来表示各个类别\n",
    "    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']  \n",
    "    if k > len(mark):  \n",
    "        print(\"Your k is too large!\")  \n",
    "        return 1  \n",
    "  \n",
    "    # 画样本点  \n",
    "    for i in range(numSamples):  \n",
    "        markIndex = int(clusterData[i, 0])  \n",
    "        plt.plot(data[i, 0], data[i, 1], mark[markIndex])  \n",
    "  \n",
    "    # 用不同颜色形状来表示各个类别\n",
    "    mark = ['*r', '*b', '*g', '*k', '^b', '+b', 'sb', 'db', '<b', 'pb']  \n",
    "    # 画质心点 \n",
    "    for i in range(k):  \n",
    "        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 20)  \n",
    "  \n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 设置k值\n",
    "k = 4  \n",
    "# centroids 簇的中心点 \n",
    "# cluster Data样本的属性，第一列保存该样本属于哪个簇，第二列保存该样本跟它所属簇的误差\n",
    "centroids, clusterData = kmeans(data, k)  \n",
    "if np.isnan(centroids).any():\n",
    "    print('Error')\n",
    "else:\n",
    "    print('cluster complete!')   \n",
    "    # 显示结果\n",
    "showCluster(data, k, centroids, clusterData)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 设置k值 \n",
    "k = 4  \n",
    "# 使用代价函数进行优化\n",
    "min_loss = 10000\n",
    "min_loss_centroids = np.array([])\n",
    "min_loss_clusterData = np.array([])\n",
    "\n",
    "for i in range(50):\n",
    "    # centroids 簇的中心点 \n",
    "    # cluster Data样本的属性，第一列保存该样本属于哪个簇，第二列保存该样本跟它所属簇的误差\n",
    "    centroids, clusterData = kmeans(data, k)  \n",
    "    loss = sum(clusterData[:,1])/data.shape[0]\n",
    "    if loss < min_loss:\n",
    "        min_loss = loss\n",
    "        min_loss_centroids = centroids\n",
    "        min_loss_clusterData = clusterData\n",
    "        \n",
    "#     print('loss',min_loss)\n",
    "print('cluster complete!')      \n",
    "centroids = min_loss_centroids\n",
    "clusterData = min_loss_clusterData\n",
    "\n",
    "# 显示结果\n",
    "showCluster(data, k, centroids, clusterData)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用肘部法则\n",
    "list_lost = []\n",
    "for k in range(2,10):\n",
    "    min_loss = 10000\n",
    "    min_loss_centroids = np.array([])\n",
    "    min_loss_clusterData = np.array([])\n",
    "    for i in range(50):\n",
    "        # centroids 簇的中心点 \n",
    "        # cluster Data样本的属性，第一列保存该样本属于哪个簇，第二列保存该样本跟它所属簇的误差\n",
    "        centroids, clusterData = kmeans(data, k)  \n",
    "        loss = sum(clusterData[:,1])/data.shape[0]\n",
    "        if loss < min_loss:\n",
    "            min_loss = loss\n",
    "            min_loss_centroids = centroids\n",
    "            min_loss_clusterData = clusterData\n",
    "    list_lost.append(min_loss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 画利用肘部法则的k值\n",
    "plt.plot(range(2,10),list_lost)\n",
    "plt.xlabel('k')\n",
    "plt.ylabel('loss')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 做预测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 做预测\n",
    "x_test = [0,1]\n",
    "np.tile(x_test,(k,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 误差\n",
    "np.tile(x_test,(k,1))-centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 误差平方\n",
    "(np.tile(x_test,(k,1))-centroids)**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 误差平方和\n",
    "((np.tile(x_test,(k,1))-centroids)**2).sum(axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 最小值所在的索引号\n",
    "np.argmin(((np.tile(x_test,(k,1))-centroids)**2).sum(axis=1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(datas):\n",
    "    return np.array([np.argmin(((np.tile(data,(k,1))-centroids)**2).sum(axis=1)) for data in datas])"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 画出簇的作用区域"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 获取数据值所在的范围\n",
    "x_min, x_max = data[:, 0].min() - 1, data[:, 0].max() + 1\n",
    "y_min, y_max = data[:, 1].min() - 1, data[:, 1].max() + 1\n",
    "\n",
    "# 生成网格矩阵\n",
    "xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),\n",
    "                     np.arange(y_min, y_max, 0.02))\n",
    "\n",
    "z = predict(np.c_[xx.ravel(), yy.ravel()])# ravel与flatten类似，多维数据转一维。flatten不会改变原始数据，ravel会改变原始数据\n",
    "z = z.reshape(xx.shape)\n",
    "# 等高线图\n",
    "cs = plt.contourf(xx, yy, z)\n",
    "# 显示结果\n",
    "showCluster(data, k, centroids, clusterData)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mini Batch K-Means算法是K-Means算法的变种，采用小批<br>\n",
    "量的数据子集减小计算时间。这里所谓的小批量是指每次训练<br>\n",
    "算法时所随机抽取的数据子集，采用这些随机产生的子集进行<br>\n",
    "训练算法，大大减小了计算时间，结果一般只略差于标准算法。<br>\n",
    "该算法的迭代步骤有两步<br>\n",
    "+ 1：从数据集中随机抽取一些数据形成小批量，把他们分配给最近的质心\n",
    "+ 2：更新质心与K均值算法相比，数据的更新是在每一个小的样本集上。<br>\n",
    "Mini Batch K-Means比K-Means有更快的 收敛速度，但同时<br>\n",
    "也降低了聚类的效果，但是在实际项目中却表现得不明显。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import MiniBatchKMeans\n",
    "model = MiniBatchKMeans(n_clusters=k)\n",
    "model.fit(data)\n",
    "centers = model.cluster_centers_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DBSCAN:\n",
    "+ DBSCAN = Density-Based Spatial Clustering of Applications with Noise\n",
    "+ 本算法将具有足够高密度的区域划分为簇，并可以发现任何形状的聚类\n",
    "+ **𝛆邻域**：给定对象半径𝜀内的区域称为该对象的𝜀邻域。\n",
    "+ **核心对象**：如果给定 𝜀 邻域内的样本点数大于等于Minpoints，则该对象为核心对象。\n",
    "+ **直接密度可达**：给定一个对象集合D，如果p在q的𝜀邻域内，且q是一个核心对象，<br>\n",
    "则我们说对象p从q触发是直接密度可达的(directly density-reachable)\n",
    "+ 密度可达：集合D，存在一个对象链$p_1,p_2\\cdots p_n,p_1=q,p_n=p$,$p_i+1$<br>\n",
    "是从$p_i$关于𝜀和Minpoints直接密度可达，则称点p是从q关于𝜀和Minpoints密度可达的。\n",
    "+ 密度相连：集合D存在点o，使得点p、q是从o关于𝜀和Minpoints密度可达的，<br>\n",
    "那么点p、q是关于𝜀和Minpoints密度相连的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DBSCAN算法思想:\n",
    "+ 1.指定合适的𝜀和Minpoints\n",
    "+ 2.计算所有的样本点，如果点p的𝜀邻域里有超过Minpoints个<br>\n",
    "点，则创建一个以p为核心点的新族。\n",
    "+ 3.反复寻找这些核心点直接密度可达（之后可能是密度可达）<br>\n",
    "的点，将其加入到相应的簇，对于核心点发生“密度相连”状况的簇，给予合并。\n",
    "+ 4.当没有新的点可以被添加到任何簇时，算法结束。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DBSCAN分析\n",
    "缺点：\n",
    "+ 当数据量增大时，要求较大的内存支持I/O消耗也很大。\n",
    "+ 当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。\n",
    "\n",
    "\n",
    "\n",
    "DBSCAN和K-MEANS比较：\n",
    "+ DBSCAN不需要输入聚类个数。\n",
    "+ 聚类簇的形状没有要求。\n",
    "+ 可以在需要时输入过滤噪声的参数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import DBSCAN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.genfromtxt(\"kmeans.txt\", delimiter=\" \")\n",
    "# 训练模型\n",
    "# eps距离阈值，min_samples核心对象在eps领域的样本数阈值\n",
    "model = DBSCAN(eps=1.5, min_samples=4)\n",
    "model.fit(data)\n",
    "result = model.fit_predict(data)\n",
    "result\n",
    "# 画出各个数据点，用不同颜色表示分类\n",
    "mark = ['or', 'ob', 'og', 'oy', 'ok', 'om']\n",
    "for i,d in enumerate(data):\n",
    "    plt.plot(d[0], d[1], mark[result[i]])\n",
    "    \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x1, y1 = datasets.make_circles(n_samples=2000, factor=0.5, noise=0.05)\n",
    "x2, y2 = datasets.make_blobs(n_samples=1000, centers=[[1.2,1.2]], cluster_std=[[.1]])\n",
    "\n",
    "x = np.concatenate((x1, x2))\n",
    "plt.scatter(x[:, 0], x[:, 1], marker='o')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "y_pred = KMeans(n_clusters=3).fit_predict(x)\n",
    "plt.scatter(x[:, 0], x[:, 1], c=y_pred)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import DBSCAN\n",
    "y_pred = DBSCAN().fit_predict(x)\n",
    "plt.scatter(x[:, 0], x[:, 1], c=y_pred)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_pred = DBSCAN(eps = 0.2).fit_predict(x)\n",
    "plt.scatter(x[:, 0], x[:, 1], c=y_pred)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_pred = DBSCAN(eps = 0.2, min_samples=50).fit_predict(x)\n",
    "plt.scatter(x[:, 0], x[:, 1], c=y_pred)\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}